package com.fang.algorithm.leecode;

/**
 * @author fanglingxiao
 * @version 1.0
 * @description 给你一个链表数组，每个链表都已经按升序排列。
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 * 示例 1：
 * <p>
 * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
 * 输出：[1,1,2,3,4,4,5,6]
 * 解释：链表数组如下：
 * [
 * 1->4->5,
 * 1->3->4,
 * 2->6
 * ]
 * 将它们合并到一个有序链表中得到。
 * 1->1->2->3->4->4->5->6
 * 示例 2：
 * <p>
 * 输入：lists = []
 * 输出：[]
 * 示例 3：
 * <p>
 * 输入：lists = [[]]
 * 输出：[]
 * @date 2022/3/6 11:31 上午
 **/
public class Test13_MergeKSortList {
    public static void main(String[] args) {
        ListNode[] nodeList = new ListNode[3];
        ListNode node00 = new ListNode(1);
        ListNode node01 = new ListNode(4);
        ListNode node02 = new ListNode(5);
        node00.next = node01;
        node01.next = node02;
        ListNode node10 = new ListNode(1);
        ListNode node11 = new ListNode(3);
        ListNode node12 = new ListNode(4);
        node10.next = node11;
        node11.next = node12;
        ListNode node20 = new ListNode(2);
        ListNode node21 = new ListNode(6);
        node20.next = node21;
        nodeList[0] = node00;
        nodeList[1] = node10;
        nodeList[2] = node20;
        ListNode mergeNode = mergeKLists(nodeList);
        print(mergeNode);
    }

    private static ListNode mergeKLists(ListNode[] nodeList) {
        if (nodeList == null) {
            return null;
        }
        if (nodeList.length < 2) {
            return nodeList[0];
        }
        ListNode head = nodeList[0];
        for (int i = 1; i < nodeList.length; i++) {
            head = mergeTwoLists(head, nodeList[i]);
        }
        return head;
    }

    private static ListNode mergeTwoLists(ListNode a, ListNode b) {
        if (a == null || b == null) {
            return a != null ? a : b;
        }
        ListNode head = new ListNode(0);
        ListNode tail = head, aPtr = a, bPtr = b;
        while (aPtr != null && bPtr != null) {
            if (aPtr.val < bPtr.val) {
                tail.next = aPtr;
                aPtr = aPtr.next;
            } else {
                tail.next = bPtr;
                bPtr = bPtr.next;
            }
            tail = tail.next;
        }
        tail.next = (aPtr != null ? aPtr : bPtr);
        return head.next;
    }

    private static void print(ListNode node) {
        if (node == null) {
            return;
        }
        while (node.next != null) {
            System.out.print(node.val + "->");
            node = node.next;
        }
        System.out.println(node.val);
    }
}
